public class Sort {
    //计数排序
    public static void countSort(int[] arr){
        //1. 遍历数组 找到最大值 和 最小值
        int max = arr[0];
        int min = arr[0];
        for (int i = 0; i < arr.length; i++) {
            if(arr[i] > max){
                max = arr[i];
            }
            if(arr[i] < min){
                min = arr[i];
            }
        }
        //2. 根据范围 定义计数数组的长度
        int len = max - min + 1;
        int count[] = new int[len];
        //3.遍历数组，在计数数组当中 记录每个数字出现的次数 O(N)
        for (int i = 0; i < arr.length; i++) {
            count[arr[i] - min]++;
        }
        //4.遍历计数数组
        int index = 0;
        for (int i = 0; i < len; i++) {
            while(count[i] > 0){
                arr[index] = i + min;
                index++;
                count[i]--;
            }
        }



    }
}
